The present invention relates to computer networking technology, and in particular to traffic engineering techniques in a multi-service class routing network.
Future Internet will support multiple classes of service in addition to best-effort service. A variety of service models have been proposed to deliver different levels of end-to-end Quality-of-Service (QoS) to applications. These services require network support of packet scheduling, signaling protocols (e.g., RSVP) and admissions policies. As diverse as these models are, there is a common theme: the network gives preferential treatment to flows in one class over flows in other classes, and bandwidth is the key QoS parameter.
A representative prototypical example of an integrated services network supports at least two different traffic classes: bandwidth-guaranteed and best-effort traffic. Bandwidth-guaranteed traffic may include both guaranteed service traffic and differentiated service traffic (differentiated service traffic may include assured forwarding and/or expedited forwarding). The network resources are shared by these two service classes. As a result of the different resource sharing models (allocation/reservation for guaranteed sessions and fair sharing for best-effort sessions), guaranteed sessions have priority over best-effort sessions. Once resources are allocated for guaranteed sessions, they are no longer available for best-effort sessions, unless the allocated resources are unused by guaranteed sessions. The packet scheduler in a router or switch ensures that the guaranteed traffic will receive, at a minimum, its allocated share of bandwidth. The portion of the link capacity available to best-effort traffic is typically allocated according to max-min fair sharing policy. Given a fixed traffic load of guaranteed sessions, the resources available to best effort traffic will be influenced by the routing for guaranteed sessions. In such a prototypical multi-class network, if the routing algorithm for guaranteed sessions ignores the load of, or even the presence of, lower priority traffic, as is commonly done, the result is that the throughput of guaranteed traffic is optimized while the performance of best-effort sessions is ignored.
With the integration of voice, video, and data traffic, the aggregate bandwidth requirement of applications is getting higher. More network infrastructures are being built with high-end routers/switches having a large number of interfaces. As a result, the network connectivity is dramatically increasing. Although ISPs do their best to configure their network topologies to match expected traffic load, the traffic load changes dynamically and the routers/switches can go down from time to time. Therefore, the network traffic load often mismatches the underlying network topology, resulting in some links being very congested while other links sit idle. Traffic engineering is an important network service that enables ISPs to balance the traffic load and improve the overall bandwidth efficiency. The importance of traffic engineering has long been recognized in the telecommunication industry and is receiving increased attention in the data networking industry, largely due to growing traffic loads and network sizes.
The main goal of traffic engineering is to achieve network resource efficiency by directing certain traffic flows to travel through some explicit routes other than the default paths determined by routing protocols, such as, for example, OSPF, EIGRP, and BGP. Conventionally, the key to achieving this goal is to select paths for selected traffic flows which meet the following two criteria:
(1) Conserve resources the selected path should consume as few resources as possible, especially when the network load is heavy; and
(2) Balance load the selected path should preferably not be congested, especially when the network load is concentrated.
These two criteria often conflict with each other: A path that consumes fewest network resources may be very congested. On the other hand, a path that is less congested may be many hops longer than the minimum-hop path to a particular node. Striking a balance between these two criteria when selecting a path has been the focus of recent studies in traffic engineering. Different service classes may deploy different resource sharing policies among their traffic flows. As a result, different traffic engineering algorithms may be used for different service classes.
While traffic engineering for individual traffic classes has been addressed in both telecommunication industry and data networking industry, traffic engineering that improves inter-class resource sharing for a network that supports multiple classes of service has received little attention. Current techniques statically partition link resources between different service classes and perform traffic engineering for each traffic class based on the resource availability for that traffic class. This approach is problematic since it is difficult if not impossible to make such a partition without either rejecting connections for guaranteed traffic (resulting in low network throughput) or causing congestion or starvation of best-effort traffic. Moreover, the traffic loads of the different traffic classes are not always evenly distributed over the network. For example, guaranteed sessions can be concentrated in one part of the network, while best-effort sessions can be concentrated in another part of the network. Static partitioning cannot adapt to such an imbalance.
Another common approach is to use the measured link utilization of both guaranteed traffic as well as best-effort traffic as the link state for the both traffic classes. This means that the traffic engineering algorithm for guaranteed traffic takes full consideration of the load conditions of best effort traffic, and routes guaranteed sessions along the links with low utilization. However, link utilization is not always a good indicator of how much bandwidth is available to reserve. For example, very bursty best-effort sessions can consume all link bandwidth, which leads to high utilization of the link, even though the link in question has reservable bandwidth. Thus, the traffic engineering algorithm for guaranteed traffic may reject a request even though reservable bandwidth is available.
Traffic engineering techniques in a multi-service class network may differ greatly from traffic engineering techniques in a single-service class network. Not only is there a need to take care of resource utilization efficiency within respective service classes, but there is also a need to avoid congestion or starvation of traffic flows having lower priority. For example, in a network that supports both bandwidth-guaranteed traffic and best-effort traffic, resources available to best-effort traffic rely on how guaranteed flows are routed. Guaranteed flows can reserve all bandwidth on certain links, thus result in congestion for, or even starvation of, best effort sessions. Additionally, statically partitioning the link resources can also result in low network throughput because of dynamic traffic mix. Thus, routing in a multi-class network is more than simply selecting for each flow an xe2x80x9coptimalxe2x80x9d path according to the routing algorithms developed for the traffic class of this flow, since such an xe2x80x9coptimalxe2x80x9d path can worsen the congestion condition of other flows belonging to different traffic classes.
It is therefore desirable to provide a multi-class traffic engineering technique which improves inter-class resource sharing efficiency and achieves high network throughput of each class of service in the network. It is also desirable to provide a multi-class traffic engineering technique that dynamically distributes link resources across different traffic classes based on load conditions of each traffic class. It is further desirable to provide a multi-class traffic engineering technique which is simple in design, and does not require modifications to existing routing algorithms employed for individual service classes within the network.
According to specific embodiments of the invention, a technique is provided for routing traffic in an integrated services network which supports a plurality of different service classes including a relative low priority class and a relative high priority class. The technique of the present invention improves inter-class resource sharing efficiency and achieves high network throughput of each class of service in the network. Additionally, the technique of the present invention dynamically distributes link resources across different traffic classes based on load conditions of each traffic class. Moreover, the technique of the present invention may be done without modifications to existing routing algorithms employed for individual service classes within the network.
According to a specific embodiment of the present invention, a method is provided for routing traffic in an integrated services network which supports a plurality of different service classes. The method includes the steps of selecting a particular service class of traffic for routing analysis; calculating link congestion of at least a portion of the network, wherein a respective residual bandwidth value and a respective link congestion index is calculated for each link within the network portion; and dynamically adjusting the calculated residual bandwidth value for each respective link within the network portion. If a selected link shows a relatively high congestion level of lower priority traffic, the residual bandwidth value for the selected link is decreased; and if a selected link shows a relatively low congestion level of lower priority traffic, the residual bandwidth value for the selected link is increased. After the residual bandwidth value for each respective link in the network portion has been dynamically adjusted according to the measured congestion of lower priority traffic on each respective link, an optimal path for routing traffic associated with the selected class of service is determined using the dynamically adjusted residual bandwidth values.
A second specific embodiment of the present invention provides a method for routing traffic associated with a selected class of service in an integrated services network which supports a plurality of different service classes. The method includes the steps of calculating, based upon a selected class of service, a virtual residual bandwidth value for each link within at least a portion of the network; and utilizing the virtual residual bandwidth values to determine an optimal path for routing traffic associated with the selected class of service. The virtual residual bandwidth values for each respective link within the network portion are calculated by adjusting the values of the respective residual bandwidth values for each link to discourage the use of links having relatively high congestion levels of lower priority traffic, and to encourage the use of links having relatively low congestion levels of lower priority traffic. To discourage the use of a particular link, a negative credit bandwidth value is added to the respective residual bandwidth value for that link, thereby yielding a virtual residual bandwidth value which is less than the actual bandwidth value for that particular link. In contrast, to encourage the use of a particular link, a positive credit bandwidth value is added to the respective residual bandwidth value for a particular link, thereby yielding a virtual residual bandwidth value that is greater than the actual residual bandwidth value for that particular link.
A third specific embodiment of the present invention provides a computer program product for use in an integrated services network which supports a plurality of different service classes. The computer program product comprises a computer usable medium having computer readable code embodied thereon for implementing a technique for routing traffic associated with a selected class of service. The computer readable code includes computer code for calculating, based on a selected class of service, a virtual residual bandwidth value for each link within at least a portion of the network; computer code for utilizing the virtual residual bandwidth values to determine an optimal path for routing traffic associated with the selected class of service; and a computer readable medium that stores the computer code. Also included within the computer program product is computer code for calculating a respective residual bandwidth value and a respective link congestion index for each link within the network portion; and computer code for utilizing the calculated residual bandwidth value and congestion index for a selected link to determine the virtual residual bandwidth value for that selected link. Additionally, the computer program product includes computer code for calculating a credit bandwidth value for each respective link in the network portion. If the congestion index for a selected link indicates a relatively high level of congestion of lower priority traffic, the credit bandwidth for a selected link is assigned a value less than zero. If, however, the congestion index for a selected link indicates a relatively low congestion level of lower priority traffic, the credit bandwidth for the selected link is assigned a value greater than zero. The computer program product further includes computer code for summing or adding the residual bandwidth value and credit bandwidth value of a selected link to determine the virtual residual bandwidth value of that link.
A fourth specific embodiment of the present invention provides an apparatus for routing traffic in an integrated services network which supports a plurality of different service classes. The apparatus includes means for selecting a particular service class of traffic for routing analysis; means for calculating link congestion of at least a portion of the network, wherein a respective residual bandwidth value and a respective link congestion index is calculated for each link within the network portion; and means for dynamically adjusting the calculated residual bandwidth value for each respective link within the network portion. If the congestion index for a selected link indicates a relatively high congestion level of lower priority traffic, the residual bandwidth value for the selected link is decreased; and if the congestion index for a selected link indicates a relatively low congestion level of lower priority traffic, the residual bandwidth value for the selected link is increased. The apparatus additionally includes means for determining an optimal path for routing traffic associated with the selected class of service using the dynamically adjusted residual bandwidth values.
The technique of the present invention provides guaranteed traffic engineering algorithms with the ability to service best-effort traffic without reducing the network throughput for guaranteed traffic. The technique uses a concept of xe2x80x9cvirtual residual bandwidthxe2x80x9d, wherein the residual bandwidth value for a link is adjusted higher or lower depending on the level congestion condition of best-effort traffic on that link. The technique discourages guaranteed traffic from using links that are already heavily loaded with best-effort traffic, and encourages links lightly loaded with best-effort traffic. Moreover, this technique may be implemented without changes to the traffic engineering algorithms deployed for individual service classes. Rather, changes are made in the link cost functions used in the traffic engineering algorithms.
Using the technique of the present invention, the distribution of network resources across traffic classes adapts dynamically and automatically to the mix of traffic in the traffic classes, even if the traffic distribution is uneven across the network. Thus, link resources are dynamically partitioned between guaranteed traffic and best-effort traffic. When the traffic load is concentrated, significant performance improvements are achieved for low priority sessions without penalizing high priority sessions.
Additional features and advantages of the present invention will become apparent from the following description of its preferred embodiments, which description should be taken in conjunction with the accompanying drawings.